package cn.chen.数据结构.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// 图类,邻接矩阵
public class Graph {

    private List<String> vertexList;    // 存储顶点
    private int[][] edges;      // 存储边的数组
    private int numEdges;       // 边的数目 ,默认为0
    private boolean[] isVisited;    // 用来记录，下标表示的元素是否被访问，下标对应值为true就是被访问了的

    public Graph(int n) {

        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        isVisited = new boolean[n];
    }
    // 获取初始结点的第一个邻接结点的下标

    /**
     * @param index 第几行
     * @return 如果找到就返回，没有就返回-1
     */
    public int getFirstAdjacentNode(int index) {

        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0)
                return i;
        }
        return -1;
    }
    // 获取第一个邻接结点的下一个邻接结点的下标

    /**
     * @param index         第几行
     * @param adjacentIndex 邻接结点的下标，要求找到该邻接结点的下一个邻接结点
     * @return 如果有就返回，没有返回-1
     */
    public int getNextAdjacentNode(int index, int adjacentIndex) {

        for (int i = adjacentIndex + 1; i < vertexList.size(); i++) {

            if (edges[index][i] > 0)
                return i;
        }
        return -1;
    }
    // 广度优先搜索
    public void bfs(){

        for(int i=0;i<isVisited.length;i++){
            isVisited[i]=false;    // 将boolean数组初始化
        }

        for(int i=0;i<vertexList.size();i++){

            bfs(i);
        }
    }
    // 广度优先搜索
    public void bfs(int index){

        if(isVisited[index]||index==-1)
            return;

        System.out.print(vertexList.get(index)+"-->");
        isVisited[index]=true;

        LinkedList queue=new LinkedList();
        queue.addLast(index);   // 将这个节点加入到队列

        while (!queue.isEmpty()){   // 只要队列不为空就一直循环

            // v就是第几行
            int v = (Integer) queue.removeFirst();  // 取出第一个元素，并且删除,
            int w= getFirstAdjacentNode(v);     // 获取v这一行的第一个邻接顶点

            while (w!=-1){

                if(!isVisited[w]){  // 没有被访问过

                    System.out.print(vertexList.get(w)+"-->");
                    isVisited[w]=true;
                    queue.addLast(w);
                }
                // 访问过
                w=getNextAdjacentNode(v,w); // 找到v这一行的下一个邻接元素
            }
        }
    }
    // 对dfs进行重载，遍历所有结点，将所有结点都当成初始结点进行深度优先搜索
    public void dfs(){

        for(int i=0;i<isVisited.length;i++){
            isVisited[i]=false;    // 将boolean数组初始化
        }
        for(int i=0;i<vertexList.size();i++){

            dfs(i); // 将每个元素都当成初始节点，进行深度优先搜索，保证不漏掉每一个节点
        }
    }
    // 深度优先搜索方法
    /**
     * @param index 元素在集合中的的索引
     */
    public void dfs(int index) {

        if(isVisited[index]||index==-1)
            return;
        System.out.print(getVertex(index)+"-->");
        isVisited[index] = true;  // 将该元素设置为已访问

        int firstAdjacentNode = getFirstAdjacentNode(index);    // 获取该元素的第一个邻接结点
        if (firstAdjacentNode != -1) {
            dfs(firstAdjacentNode); // 递归

            int nextAdjacentNode = getNextAdjacentNode(index, firstAdjacentNode);   // 获取第一个邻接结点的下一个邻接结点
            while (nextAdjacentNode != -1) {    // 循环获取下一个邻接结点，直到没有邻接结点

                dfs(nextAdjacentNode);  // 递归
                nextAdjacentNode = getNextAdjacentNode(index, nextAdjacentNode);
            }
        }
    }

    // 插入顶点
    public void addVertex(String vertex) {

        vertexList.add(vertex);
    }
    // 添加边
    /**
     * v1，v2其实就是边的两个顶点的顺序的索引
     *
     * @param v1
     * @param v2
     * @param weight
     */
    public void addEdge(int v1, int v2, int weight) {

        // 无向图，对称的
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numEdges++;
    }

    // 返回节点的个数
    public int getNumVertex() {

        return vertexList.size();
    }

    // 得到边的数目
    public int getNumEdges() {

        return this.numEdges;
    }

    // 返回节点index(下标)对应的值
    public String getVertex(int index) {

        return vertexList.get(index);
    }

    // 返回v1，v2的权值
    public int getWeight(int v1, int v2) {

        return edges[v1][v2];
    }

    // 显示图对应的矩阵
    public void showGraph() {

        if (edges == null) {

            System.out.println("矩阵为空");
            return;
        }
        for (int[] i : edges) {

            for (int j : i) {

                System.out.printf("%d\t", j);
            }
            System.out.println();
        }
    }
}
     